package com.zjsru.plan2025.oneday;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 2080. 区间内查询数字的频率
 *
 * @Author: cookLee
 * @Date: 2025-02-18
 */
public class RangeFreqQuery {

    /**
     * RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
     * int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。
     * \
     * 输入：
     * ["RangeFreqQuery", "query", "query"]
     * [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
     * 输出：
     * [null, 1, 2]
     * <p>
     * 解释：
     * RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
     * rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
     * rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        //方法一超出时间限制
    }

    int[] temp;
//    超出时间限制
//    public RangeFreqQuery(int[] arr) {
//        this.temp = new int[arr.length];
//        System.arraycopy(arr, 0, this.temp, 0, arr.length);
//    }
//
//    public int query(int left, int right, int value) {
//        int count = 0;
//        for (int i = left - 1; i < right - 1; i++) {
//            if (this.temp[i] == value) {
//                count++;
//            }
//        }
//        return count;
//    }

    Map<Integer, List<Integer>> idxSameValue;

    /**
     * 哈希
     *
     * @param arr arr
     */
    public RangeFreqQuery(int[] arr) {
        this.idxSameValue = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            //按照元素作为Key转化哈希表，value作为下标的集合
            this.idxSameValue.putIfAbsent(arr[i], new ArrayList<>());
            this.idxSameValue.get(arr[i]).add(i);
        }
    }

    public int query(int left, int right, int value) {
        if (!this.idxSameValue.containsKey(value)) {
            return 0;
        }
        //获取value存在对应的数组
        List<Integer> idx = this.idxSameValue.get(value);
        //通过二分按照左右指针，找到第一个大于等于left的元素，然后找到第一个大于right的元素，然后返回两个下标之间的差值
        int leftCount = this.findSubByLeftHelper(idx, left);
        int rightCount = this.findSubByRightHelper(idx, right);
        return rightCount - leftCount;
    }

    private int findSubByLeftHelper(List<Integer> idx, int left) {
        int l = 0, r = idx.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (idx.get(mid) >= left) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;

    }

    private int findSubByRightHelper(List<Integer> idx, int right) {
        int l = 0, r = idx.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (idx.get(mid) > right) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }


}
